package dp;
import java.util.*;
public class _18_279_完全平方数 {
    public static int numSquares(int n) {
    	List<Integer> list = new ArrayList<>();
    	// 先把小于n的所有完全平方数得到
    	list.add(1);
    	for(int i = 1; i <= n; i++) {
    		for(int j = 1; j < i; j++) {
    			if(j*j == i) {
    				list.add(i);
    			}
    		}
    	}
    	int dp[] = new int[n+1];
    	dp[0] = 0;
    	for(int i = 1; i <= n; i++) {
    		dp[i] = Integer.MAX_VALUE;
    	}
    	// 完全背包遍历所有组合，拿到组成n最少次数的组合
    	for(int i = 0; i < list.size(); i++) {
    		for(int j = list.get(i); j <= n; j++) {
    			// 这里的判断用不用都可以，因为本题不存在凑不成的情况，一定可以用1组成任意一个n
//    			if(dp[j - list.get(i)] != Integer.MAX_VALUE) {
    				dp[j] = Math.min(dp[j], dp[j-list.get(i)] + 1);
//    			}
    		}
    	}
    
    	
    	return dp[n];
    }
    
    public static void main(String[] args) {
    	System.out.println(numSquares(4));
	}
}
